#include <iostream>
#include <vector>
#include <stack>
#include <unordered_set>
using namespace std;

class Solution {
public:
    vector<int> sumOfDistancesInTree(int N, vector<vector<int>>& edges) {
        vector<int> res;
        if (N == 0) {
            return res;
        }

        // 初始化中间结果存储空间
        vector<int> tmpVec(N, -1);
        middRes.assign(N,tmpVec);

        // 根据输入，创建无向图
        CreateGraph(N, edges);
        totalVertex = N;


        int sum;
        for (int from  = 0; from < N; ++from) {
            sum = 0;
            for (int to = 0; to < N; ++to) {
                sum += myDist(from, to);
            };
            res.emplace_back(sum);
        }
        return res;
    }
private:
    void CreateGraph(int N, vector<vector<int>>& edges);
    //  计算后同时将结果写进中间结果存储空间
    int myDist(int from, int to);
    bool dfs(vector<bool> &isAcc, int &dist, int start, const int &target);
    // 存储无向图
    vector<vector<bool>> undirectedGraph;

    vector<vector<int>> middRes; // 存储已经计算出的距离，可以重用，防止重复计算

    int totalVertex;
};

void Solution::CreateGraph(int N, vector<vector<int>>& edges)
{
    // 建立无向图
    undirectedGraph.assign(N, vector<bool>(N, false));
    for (auto &edge : edges) {
        undirectedGraph[edge[0]][edge[1]] = true;
        undirectedGraph[edge[1]][edge[0]] = true;
    }
}
int  Solution::myDist(int from, int to)
{
    if (from == to) {
        return 0;
    }

    if (from > to) {
        return middRes[to][from];
    }
    vector<bool> isAcc(totalVertex, false);
    isAcc[from] = true;
    int dist = 0;
    dfs(isAcc, dist, from, to);
    middRes[from][to] = dist;
    return dist;
}

bool Solution::dfs(vector<bool> &isAcc, int &dist, int start, const int &target)
{
    for (int counter = 0; counter < totalVertex; ++counter) {
        if (undirectedGraph[start][counter] == true && isAcc[counter] == false) {
            ++dist;
            isAcc[counter] = true;
            if (counter == target) {
                return true;
            }
            if (dfs(isAcc, dist, counter, target)) {
                return true;
            } else {
                --dist;
            }
        }
    }
    return false;
}